package 链表.链表逆置;

import java.util.List;

/**
 * @author: wh(1835734390 @ qq.com)
 * @date: 2022/11/24 15:42
 * @description:链表逆置
 * @version:
 */
public class Solution {
    public static void main(String[] args) {
        ListNode listNode = new ListNode(1,new ListNode(2,new ListNode(3,new ListNode(4))));
        ListNode node = reverseList3(listNode);
        System.out.println(node.val);
    }


    public static ListNode reverseList(ListNode head) {
        ListNode r = null;
        while(head != null){
            ListNode q = head.next;
            //反向使用尾插法
            head.next = r;
            r = head;
            head = q;
        }
        return r;
    }


    //TODO 这里使用头插法在力扣的编译器中无法通过
    public static ListNode reverseList3(ListNode head){
        ListNode root = new ListNode(0);
        root.next = head;
        ListNode p = head;
        while (p != null){
            ListNode q = p.next;
            p.next = root.next;
            root.next = p;
            p = q;
        }
        return root.next;
    }

}
